1. Field of the Invention
The invention relates to linear feedback shift-registers (LFSRs) and more particularly to an LFSR module comprising parallel LFSRs.
2. Description of the Related Art
Linear feedback shift-register (LFSR) circuits have been used to create parity check to enhance data integrity in complex very large scale integrated (VLSI) circuits containing thousands of interconnected circuits. LFSRs have also produced signatures at the outputs of a DUT (device under test) to represent current states corresponding to prior states and received response signals.
Reviewing first some pertinent principles that govern LFSRs, FIG. 1 shows a conventional sequential LFSR 100 for generating an output stream OUT according to an input stream IN={I0, I1, I2, . . . , IL−1}, where L denotes the symbol number of the input stream IN. As shown, the LSFR 100 comprises a plurality of stages 110(0)-110(X), an end stage 120 and an output generator 130. The stages can be implemented as a beginning stage 110(0), at least one intermediate stage of stages 110(1)-110(X), and an end stage 120. The input stream IN and the intermediate stream Rx are provided sequentially to a summing device 121 in the end stage 120 for generating the feedback stream SF. The feedback stream SF is then fed into all of the beginning and intermediate stages 110(0)-110(X). Each beginning stage and intermediate stage 110[i] comprises a logic network 111[i] and a registering device 112[i] (such as the flip flop shown in FIG. 1) for respectively generating an intermediate stream Ri and storing the received symbol of the intermediate stream Ri. The logic network 111[i] comprises a multiplier 114[i] multiplying the symbol of the feedback stream SF[i] by a respective multiplication factor Ci and an adding device 115(i) (except in the beginning stage 110(0)) adding output symbol of the multiplier 114[i] and the symbol of the intermediate stream R(i−1) received from the preceding stage for generating the intermediate stream Ri, wherein ‘i’ described above is from 0 to X. Because the registering devices are clocked through subsequent clock cycles, one symbol of the input stream IN is fed into the end stage 120 and symbols of the intermediate streams R0-RX stored in the registering devices in one stage are shifted to the next stage. The symbols of the intermediate stream Ri generated after the nth symbol of the fed input stream may thus be expressed as Ri(n), where 0≦n≦L−1. It is noted that the symbol can express a segment having several corresponding bits of the sub-output streams of the LFSRs.
The output generator 130 comprises a switch 131 initially set to output the intermediate stream IN={I0, . . . , IL−1}. After all symbols of the input stream IN are fed into and processed in the stages, the last generated symbols R0(L−1)-RX(L−1) of the intermediate streams R1-RX are sequentially provided to output generator 130 to act as the succeeding symbols of the output stream OUT. Accordingly, the output stream OUT comprises {O1, O2, . . . , OX}={I0, I1, . . . IL−1. RX(L−1), R1[L−1], . . . , R0(L−1)}. In some applications, the last generated symbols R0(L−1)-RX(L−1) of the intermediate streams R1-RX may be provided directly as the output stream OUT, that is, the output stream OUT comprises {O1, O2, . . . , OX}={RX(L−1), . . . , R1[L−1], R0(L−1)}.
The identity of the LFSR 100 can be characterized by means of a polynomial (a so called characteristic polynomial) expression with coefficients corresponding to the multiplication factors C0-CX of the multipliers 114[0]-114[X]. Thus, the characteristic polynomial for the LFSR 100 of FIG. 1 is:
      P    ⁡          (      x      )        =                    ∑                  i          =          0                X            ⁢                        C          i                ⁢                  x          i                      +                  x                  X          +          1                    .      
In polynomial expressions, the LFSR module 100 is implemented as a finite field polynomial divider where the input stream IN corresponds to a dividend polynomial D(x), the characteristic polynomial corresponds to a divisor polynomial P(x), the feedback stream SF corresponds to a quotient polynomial, corresponding symbols R1(n)-RX(n) generated at one clock cycle of the intermediate streams R0-RX correspond to an intermediate remainder polynomial generated during division of the dividend polynomial D(x) by the characteristic polynomial P(x), and the output stream OUT in the form of {R0(L−1), R1[L−1], . . . , RX(L−1)}corresponds to a remainder polynomial R[x] of the dividend polynomial D(x) divided by the characteristic polynomial [divisor polynomial] P(x). That is, D(x)=P(x)Q[x]+R[x], wherein Q[x] is a quotient polynomial.
Classic LFSRs, as described in FIG. 1, are sequential. Values are shifted from one shift-register stage to the next by a clock until they eventually exit via an LFSR output. It is well known that sequential operations are slow in nature and must therefore be compensated by running the LFSR at high speeds. For high end systems, high speed data generation and compression can only be achieved by high performance circuits and a high speed clock. High speed circuits have high power and thermal requirements, consuming considerably more system space.